//为完成教材练习题而写的类，已通过教材给出的测试样例，但没有考虑一些特殊情况
public class Geometry {
    //判断线段是否相交
    //p,q是线段的两个端点
    public static boolean doesSegmentIntersect(Point p1, Point q1, Point p2, Point q2) {
        Point intersetPoint = calcIntersectPoint(p1, q1, p2, q2);
        if (intersetPoint == null) return false;
        double x = intersetPoint.x;
        double y = intersetPoint.y;
        //确保交点位于线段上
        if (x >= Math.min(p1.x, q1.x) && x <= Math.max(p1.x, q1.x)
                && x >= Math.min(p2.x, q2.x) && x <= Math.max(p2.x, q2.x)) return true;
        else return false;
    }

    //判断线段是否相交
    //端点处相交返回false
    public static boolean doesSegmentIntersectInternally(Point p1, Point q1, Point p2, Point q2) {
        Point intersetPoint = calcIntersectPoint(p1, q1, p2, q2);
        if (intersetPoint == null) return false;
        double x = intersetPoint.x;
        double y = intersetPoint.y;
        //确保交点位于线段上
        if (x > Math.min(p1.x, q1.x) && x < Math.max(p1.x, q1.x)
                && x > Math.min(p2.x, q2.x) && x < Math.max(p2.x, q2.x)) return true;
        else return false;
    }

    public static Point calcIntersectPoint(Point p1, Point q1, Point p2, Point q2) {
        double a = p1.y - q1.y;
        double b = p1.x - q1.x;
        double c = p2.y - q2.y;
        double d = p2.x - q2.x;
        double e = (p1.y - q1.y) * p1.x - (p1.x - q1.x) * p1.y;
        double f = (p2.y - q2.y) * p2.x - (p2.x - q2.x) * p2.y;
        final double eps = 1e-6;
        if (Math.abs(a * d - b * c) < eps) return null; //平行
        //交点坐标
        double x = (e * d - b * f) / (a * d - b * c);
        double y = (a * f - e * c) / (a * d - b * c);
        return new Point(x, y);
    }
}
